public class Solution390 {
    public int lastRemaining(int n) {
        int firstNum = 1, diff = 1, count = n, direct = 0;
        for (; count > 1; diff *= 2, count /= 2, direct = (direct + 1) % 2) {
            if(direct == 0 || (count & 1) == 1){
                firstNum += diff;
            }
        }
        return firstNum;
    }

    public static void main(String[] args) {
        Solution390 s = new Solution390();
        System.out.println(s.lastRemaining(9));
    }
}
